#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 1;
        ListNode* newhead = nullptr;
        ListNode* tail = head;
        ListNode* prev = head;
        while (tail)
        {
            if (n == k)
            {
                n = 1;
                if (newhead == nullptr)
                {
                    ListNode* p = head;
                    while (prev != tail)
                    {
                        ListNode* next = prev->next;
                        prev->next = p;
                        p = prev;
                        prev = next;
                    }
                    tail = tail->next;
                    prev->next = p;
                    newhead = prev;
                    prev = head;
                    prev->next = tail;
                }
                else
                {
                    ListNode* ph = prev;
                    ListNode* p = prev->next;
                    while (p != tail)
                    {
                        ListNode* next = p->next;
                        p->next = prev;
                        prev = p;
                        p = next;
                    }
                    tail = tail->next;
                    p->next = prev;
                    prev = ph->next;
                    ph->next = p;
                    prev->next = tail;
                }
            }
            else
            {
                n++;
                tail = tail->next;
            }
        }
        return newhead;
    }
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int k = Size(head);
        if (k < n)
        {
            return nullptr;
        }
        else if (k == n)
        {
            ListNode* newhead = head->next;
            delete head;
            return newhead;
        }
        int i = 1;
        ListNode* tail = head;
        while (1)
        {
            if (i + n == k)
            {
                ListNode* next = tail->next;
                tail->next = next->next;
                delete next;
                return head;
            }
            else
            {
                i++;
                tail = tail->next;
            }
        }
        return head;
    }
    int Size(ListNode* head)
    {
        int n = 0;
        ListNode* tail = head;
        while (tail)
        {
            tail = tail->next;
            n++;
        }
        return n;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr)
        {
            return nullptr;
        }
        ListNode* tail = head->next;
        ListNode* prev = head;
        ListNode* pprev = nullptr;
        ListNode* newhead = head;
        while (tail)
        {
            if (prev == nullptr || tail->val != prev->val)
            {
                pprev = prev;
                prev = tail;
                tail = tail->next;
            }
            else
            {
                while (tail && tail->val == prev->val)
                {
                    ListNode* next = tail->next;
                    delete tail;
                    tail = next;
                }
                if (pprev == nullptr)
                {
                    delete prev;
                    prev = nullptr;
                    pprev = nullptr;
                    newhead = tail;
                }
                else
                {
                    delete prev;
                    pprev->next = tail;
                    prev = pprev;
                }
            }
        }
        return newhead;
    }
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k)
    {
        if (head == nullptr)
        {
            return nullptr;
        }
        int n = Size(head);
        k %= n;
        if (k == 0)
        {
            return head;
        }
        ListNode* newhead = head;
        int i = 1;
        while (i)
        {
            if (i + k == n)
            {
                ListNode* prev = newhead;
                newhead = newhead->next;
                prev->next = nullptr;
                ListNode* tail = newhead;
                while (tail->next)
                {
                    tail = tail->next;
                }
                tail->next = head;
                break;
            }
            else
            {
                i++;
                newhead = newhead->next;
            }
        }
        return newhead;
    }
    int Size(ListNode* head)
    {
        int n = 0;
        ListNode* tail = head;
        while (tail)
        {
            tail = tail->next;
            n++;
        }
        return n;
    }
};